//estimate the expected number of points left
#include <stdio.h>
#include "uniform.c"

#define MAX 50 //the maximum number of points is 100 

#define MIN 2 //the minimum number of points is 2,it should not smaller than 2

#define T 100 //repeat every number of points 100 times

double uniform(double *);

int main() {

  int x,i,j,n,sum;
  double seed;
  int p[MAX]={0}; //label of every points
  double sp[MAX]={0}; // number of left points in one term
  for (n=MIN;n<=MAX;n++){
	  for (j=0;j<T;j++){
		  seed = 1234567+j*100000; //set the seed differently
		  for (i=1; i <= n; i++){ //set the initial value of label of every points
			  p[i-1]=i;
		  }
		  sum=1;
		  while(sum!=0){
			  sum=0;
			  x=uniform(&seed)*(n-1)+1; ////generate an uniform number x within 1~n 
			  if (p[x-1]*p[x]!=0){ //the pairs of points can be chosen
				  p[x-1]=0;
				  p[x]=0;
			  }
			  for (i=1; i < n; i++) { //check if all points left can not be paired
				  sum=sum+p[i-1]*p[i];
			  }
		  }
		  for (i=1; i <= n; i++) { //compute the number of these points
			  if (p[i-1]!=0) {
				  sp[n-1]++;
			  }
		  }
	  }
	  sp[n-1]=sp[n-1]/T;
  }
  printf("\n n vs. the number of points left");
  for (n=MIN;n<=MAX;n++){
	  printf("\n %d\t ",n);
	  for (i=1; i < 5*sp[n-1]; i++)
		  printf("*"); //print the graph of the "n vs. the number of points left"
  }
  printf("\n n vs. the value of (n+2)/e^2");
  for (n=MIN;n<=MAX;n++){
	  printf("\n %d\t ",n);
	  for (i=1; i < 5*(n+2)/2.718/2.718; i++)
		  printf("*"); //print the graph of the "n vs. the value of (n+2)/e^2"
  }
  printf("\n");
}
      
      
      
    

